#include <cstring>
#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

extern "C" {
// 图结构
struct Graph {
    std::unordered_map<int, std::vector<int>> adjList;
    std::vector<std::pair<int, int>> edges;
    int nodeCount;
};

// 创建图
Graph *create_graph() {
    return new Graph();
}

// 添加节点
void add_node(Graph *graph, int node) {
    if (graph->adjList.find(node) == graph->adjList.end()) {
        graph->adjList[node] = std::vector<int>();
        graph->nodeCount++;
    }
}

// 添加边
void add_edge(Graph *graph, int u, int v) {
    add_node(graph, u);
    add_node(graph, v);
    graph->adjList[u].push_back(v);
    graph->adjList[v].push_back(u);  // 无向图
    graph->edges.push_back(std::make_pair(u, v));
}

// 获取节点数
int get_node_count(Graph *graph) {
    return graph->nodeCount;
}

// 获取边数
int get_edge_count(Graph *graph) {
    return graph->edges.size();
}

// 销毁图
void destroy_graph(Graph *graph) {
    delete graph;
}

// DFS 回调函数类型
typedef void (*DFSCallback)(int node, int depth, const char *status);

// 深度优先搜索
void dfs(Graph *graph, int start, DFSCallback callback) {
    std::unordered_map<int, bool> visited;
    std::stack<std::pair<int, int>> stack;  // <节点, 深度>

    stack.push(std::make_pair(start, 0));

    while (!stack.empty()) {
        auto current = stack.top();
        stack.pop();
        int node = current.first;
        int depth = current.second;

        if (!visited[node]) {
            // 调用回调 - 访问节点
            if (callback) callback(node, depth, "VISIT");

            visited[node] = true;

            // 遍历邻居
            for (int neighbor : graph->adjList[node]) {
                if (!visited[neighbor]) {
                    // 调用回调 - 发现新节点
                    if (callback) callback(neighbor, depth + 1, "DISCOVER");
                    stack.push(std::make_pair(neighbor, depth + 1));
                }
            }

            // 调用回调 - 完成节点处理
            if (callback) callback(node, depth, "COMPLETE");
        }
    }
}
}